#include <vector>
#include <iostream>

using namespace std;

int minNumberOfCoinsXYN(vector<int> coins, int n)
{
  sort(coins.begin(), coins.end());
  int a = 0;
  vector<int> x(n + 1, 0);
  auto b = x.begin();
  auto c = coins.end() - 1;
  auto r = 0;
  auto d = 0;
  while (b != x.end())
  {
    if (r + *c > coins.size())
    {
      c--;
    }
    else
    {
      for (size_t i = 0; i < *c; i++)
      {
        b++;
        r += 1;
      }
      d += 1;
    }

  }
  return d;
}

int numberOfWaysToMakeChangeZHX(vector<int> coins, int n)
{
    // 创建一个包含 n+1 的元素的数组 ways，表达找从 0 至 n 钱的方法。
    // 并且将ways中每个元素初始化为0
    vector<int> ways(n + 1, 0);

    // ++++++中心思想++++++
    // 要计算n相对于面额k的找钱方法，只需计算n-k的相对于面额k的方法数，以此类推
    // 理解当面额k为面额数组k[k1,k2,...kn]时，那么计算n相对于面额数组k的找钱方法，只需计算n-k的相对于面额数组k的方法数，以此类推
    // ++++++中心思想++++++

    // 遍历所有的面额
    // 对于每一种面额，我们用它去遍历所有要找的钱数
    // 如果能找
    //    更新对应找钱上的方法数 ways[b(找钱)] + ways[b(找钱) - a(面额)]
    // 否则
    //    PASS
    // 所有面额遍历结束，ways 最后一个元素的值，就是答案

    //初始化ways[0]为1，表示找钱0即找开了，记1次
    ways[0] = 0;

    //循环每一种面额
    for (int j = 0; j < coins.size(); j++)
    {
        //循环计算1到n中所有数的相对于一种面额的找钱情况
        for (int i = 1; i <= n; i++)
        {
            //如果面额小于要找开的钱数
            if (coins[j] <= i)
            {
                //把要找钱i的方法数和i-coins[j]的找钱方法数+1做比较，小的存起来
                if(ways[i] == 0 || 1 + ways[i - coins[j]] < ways[i])
                    ways[i] = 1 + ways[i - coins[j]];
            }
                
        }
        //打印每一种面额计算完成后ways中的值
        for (int k = 0; k < ways.size(); k++)
        {
            cout << k << "=" << ways[k] << endl;
        }

        //打印“--”用作分隔，便于查看ways中间值
        cout << "----------------------------------------" << endl;

    }
    
    //返回ways中最后一个元素的值，即是我们要计算要找钱n的方法数
    return (*(ways.end() - 1));
}

int main(int argc, char const *argv[]) {
  // cout<<minNumberOfCoinsXYN({1, 5, 10}, 7)<<endl;
  cout<<numberOfWaysToMakeChangeZHX({1, 5, 10}, 7)<<endl;
  return 0;
}
